Λεκτική ανάλυση

Στην πληροφορική, λεκτική ανάλυση (lexical analysis) είναι η διαδικασία που μετατρέπει μια ακολουθία από χαρακτήρες σε μια ακολουθία από λεκτικές μονάδες (tokens). Ένα πρόγραμμα ή συνάρτηση που κάνει λεκτική ανάλυση ονομάζεται λεκτικός αναλυτής (lexical analyzer, lexer ή scanner). Ένας λεκτικός αναλυτής συχνά αποτελεί μια συνάρτηση που καλείται από ένα συντακτικό αναλυτή ή κάποια άλλη συνάρτηση.

Λεκτική γραμματική

Ο ορισμός μιας γλώσσας προγραμματισμού συχνά περιλαμβάνει ένα σύνολο κανόνων που ορίζουν τον λεκτικό αναλυτή. Αυτοί οι κανόνες συνήθως είναι κανονικές εκφράσεις και περιγράφουν το σύνολο των επιτρεπτών ακολουθιών χαρακτήρων που μπορούν να χρησιμοποιηθούν για να σχηματίσουν μεμονωμένες λεκτικές μονάδες (tokens ή lexemes). Ένα πρόγραμμα λεκτικής ανάλυσης αναγνωρίζει συμβολοσειρές. Για κάθε συμβολοσειρά που εντοπίζει, το πρόγραμμα ακολουθεί κάποια ενέργεια.

Στις γλώσσες προγραμματισμού που χωρίζουν τμήματα κώδικα (blocks) με μονάδες (όπως το "{" και το "}"), και όχι με στοίχιση, οι χαρακτήρες κενού (white space) ορίζονται και αυτοί από μια κανονική έκφραση, επηρεάζοντας έτσι την αναγνώριση των άλλων μονάδων, χωρίς όμως το ίδιο το κενό να αναγνωρίζεται σαν μονάδα. Δηλαδή, σε αυτές τις γλώσσες, οι χαρακτήρες κενού δεν είναι σημαντικοί.

Λεκτική μονάδα

Μια λεκτική μονάδα (token) είναι μια ακολουθία από χαρακτήρες που έχουν καταχωρηθεί ανάλογα με τους κανόνες ως κάποιο σύμβολο (π.χ., IDENTIFIER, NUMBER, COMMA). Η διαδικασία σχηματισμού λεκτικών μονάδων από ένα ρεύμα εισόδου χαρακτήρων ονομάζεται tokenization και ο λεκτικός αναλυτής κατηγοριοποιεί τις μονάδες ανάλογα με τον τύπο συμβόλου τους. Μια μονάδα μπορεί να μοιάζει με οτιδήποτε μπορεί να χρησιμοποιηθεί για την επεξεργασία ενός ρεύματος εισόδου κειμένου ή ενός αρχείου κειμένου.

Ένας λεκτικός αναλυτής γενικά δεν επεξεργάζεται συνδυασμούς λεκτικών μονάδων αλλά αυτό αποτελεί έργο του συντακτικού αναλυτή. Για παράδειγμα, ένας κλασικός λεκτικός αναλυτής αναγνωρίζει κάθε παρένθεση σαν ξεχωριστή λεκτική μονάδα, αλλά δεν ελέγχει αν κάθε παρένθεση που ανοίγει αντιστοιχεί σε μια παρένθεση που κλείνει.

Έστω η εξής έκφραση στη γλώσσα προγραμματισμού C:

sum = 3 + 2;

Οι λεκτικές μονάδες εμφανίζονται στον εξής πίνακα:

Lexeme	Τύπος λεκτικής μονάδας
sum	Αναγνωριστικό (identifier)
=	Τελεστής ανάθεσης
3	Ακέραια τιμή
+	Τελεστής πρόσθεσης
2	Ακέραια τιμή
;	Τέλος εντολής

Οι λεκτικές μονάδες συχνά ορίζονται από κανονικές εκφράσεις, οι οποίες γράφονται με τη βοήθεια λογισμικού παραγωγής λεκτικών αναλυτών, όπως το lex. Ο λεκτικός αναλυτής (που μπορεί να έχει παραχθεί αυτόματα από κάποιο εργαλείο όπως το lex, ή να έχει γραφτεί στο χέρι) διαβάζει ένα ρεύμα από χαρακτήρες, βρίσκει τις λεκτικές μονάδες και τις κατηγοριοποιεί. Αυτό ονομάζεται "tokenizing". Αν ο λεκτικός αναλυτής βρει κάποια μη επιτρεπτή λεκτική μονάδα, αναφέρει σφάλμα.

Την παραπάνω διαδικασία ακολουθεί η συντακτική ανάλυση. Από εκεί, τα ερμηνευμένα δεδομένα μπορούν να αποθηκευτούν σε δομές δεδομένων για γενική χρήση, διερμηνεία, ή μεταγλώττιση.

Scanner

Το πρώτο στάδιο, ο scanner, συνήθως βασίζεται σε κάποια μηχανή πεπερασμένων καταστάσεων (finite-state machine, FSM). Περιλαμβάνει κωδικοποιημένη πληροφορία για όλες τις πιθανές ακολουθίες χαρακτήρων που μπορούν να βρίσκονται σε κάθε λεκτική μονάδα που αναγνωρίζει (κάθε τέτοια ακολουθία χαρακτήρων ονομάζεται lexeme). Για παράδειγμα, μια λεκτική μονάδα ακέραιος μπορεί να περιλαμβάνει οποιαδήποτε ακολουθία αριθμητικών ψηφίων. Πολλές φορές, ο πρώτος χαρακτήρας που δεν είναι κενό μπορεί να χρησιμοποιηθεί για να βρεθεί το είδος της λεκτικής μονάδας που ακολουθεί και στη συνέχεια γίνεται επεξεργασία όλων των χαρακτήρων που ακολουθούν μέχρι να βρεθεί κάποιος χαρακτήρας που δεν είναι αποδεκτός (αυτός ο κανόνας ονομάζεται maximal munch ή longest match). Σε κάποιες γλώσσες ο εντοπισμός των λεκτικών μονάδων μπορεί να είναι πιο πολύπλοκος και να περιλαμβάνει οπισθοχώρηση (backtracking) σε σχέση με χαρακτήρες που έχουν ήδη διαβαστεί.

Tokenizer

Tokenization ονομάζεται η διαδικασία με την οποία τεμαχίζεται μια συμβολοσειρά χαρακτήρων εισόδου σε ξεχωριστά μέρη, καθώς και η κατηγοριοποίηση αυτών των μερών. Οι λεκτικές μονάδες που προκύπτουν προωθούνται στη συνέχεια για περαιτέρω επεξεργασία. Η διαδικασία αυτή μπορεί να θεωρηθεί μέρος της συντακτικής ανάλυσης της εισόδου.

Έστω για παράδειγμα, η συμβολοσειρά:

The quick brown fox jumps over the lazy dog

Αν και ένας ομιλητής της Αγγλικής θα χώριζε την παραπάνω πρόταση με βάση τα κενά, αυτό δεν συμβαίνει γενικά κατά τη συντακτική ανάλυση. Η είσοδος αποτελείται από 43 χαρακτήρες και πρέπει ρητά να χωριστεί σε 9 λεκτικές μονάδες χρησιμοποιώντας σαν διαχωριστικό το κενό (π.χ. ίσο με τη συμβολοσειρά " " ή την κανονική έκφραση /\s{1}/).

Οι λεκτικές μονάδες θα μπορούσαν επίσης να αναπαρασταθούν ως XML:

<sentence>
  <word>The</word>
  <word>quick</word>
  <word>brown</word>
  <word>fox</word>
  <word>jumps</word>
  <word>over</word>
  <word>the</word>
  <word>lazy</word>
  <word>dog</word>
</sentence>

Θα μπορούσαν επίσης να αναπαρασταθούν ως s-expression:

 (sentence
   ((word The) (word quick) (word brown) 
    (word fox) (word jumps) (word over) 
    (word the) (word lazy) (word dog)))

Ένα lexeme είναι απλά μια ακολουθία από χαρακτήρες που είναι γνωστός ο τύπος τους (για παράδειγμα, μια ρητή συμβολοσειρά ή μια ακολουθία από γράμματα). Για να κατασκευαστεί η λεκτική μονάδα, ο λεκτικός αναλυτής χρειάζεται ένα δεύτερο στάδιο, τον evaluator, που διαβάζει τους χαρακτήρες αυτούς για να κατασκευάσει μια τιμή (value). Ο τύπος του lexeme συνδυάζεται με την τιμή του για να προκύψει μια λεκτική μονάδα, η οποία δίνεται στον συντακτικό αναλυτή. Υπάρχουν λεκτικές μονάδες, όπως οι παρενθέσεις, που δεν έχουν στην πραγματικότητα τιμές, και ο evaluator μπορεί να επιστρέφει κενές τιμές για αυτές, σε αντίθεση με πιο πολύπλοκες περιπτώσεις, όπως οι ακέραιοι, τα αναγνωριστικά και οι συμβολοσειρές. Υπάρχουν περιπτώσεις που ο evaluator αγνοεί εντελώς κάποιο lexeme, κρύβοντάς το από τον συντακτικό αναλυτή, κάτι που είναι χρήσιμο στην περίπτωση των κενών χαρακτήρων και των σχολίων.

Για παράδειγμα, στον πηγαίο κώδικα ενός προγράμματος, η συμβολοσειρά

net_worth_future = (assets - liabilities);

μπορεί να μετατραπεί (αγνοώντας τους κενούς χαρακτήρες) στο εξής ρεύμα λεκτικών μονάδων:

NAME "net_worth_future" 
EQUALS 
OPEN_PARENTHESIS 
NAME "assets" 
MINUS 
NAME "liabilities" 
CLOSE_PARENTHESIS 
SEMICOLON

Αν και είναι πιθανό (και κάποιες φορές απαραίτητο, αν υπάρχουν νομικοί περιορισμοί ή για γραμματικές με λίγες λεκτικές μονάδες) να γραφτεί κάποιος λεκτικός αναλυτής με το χέρι, συνήθως οι λεκτικές αναλυτές κατασκευάζονται αυτόματα από εργαλεία. Αυτά τα εργαλεία συνήθως δέχονται κανονικές εκφράσεις που περιγράφουν τις λεκτικές μονάδες που επιτρέπονται στο ρεύμα εισόδου. Κάθε κανονική έκφραση αντιστοιχίζεται με έναν κανόνα παραγωγής της γραμματικής της γλώσσας προγραμματισμού που αποτιμά τα lexeme που ταιριάζουν με την κανονική έκφραση. Αυτά τα εργαλεία μπορούν να παράγουν πηγαίο κώδικα προς μεταγλώττιση και εκτέλεση, ή να κατασκευάσουν έναν πίνακα μεταβάσεων καταστάσεων μιας μηχανής πεπερασμένων καταστάσεων (η οποία στη συνέχεια συνδέεται με άλλο κώδικα που πρόκειται να μεταγλωττιστεί και να εκτελεστεί).

Οι κανονικές εκφράσεις αναπαριστούν με συντομία τις διάφορες μορφές που μπορούν να έχουν τα lexeme. Για παράδειγμα, σε μια γλώσσα βασισμένη στα Αγγλικά, μια λεκτική μονάδα NAME μπορεί να είναι κάθε αλφαβητικός χαρακτήρας των Αγγλικών ή μια κάτω παύλα, ακολουθούμενα από έναν αριθμό αλφαριθμητικών χαρακτήρων ASCII ή κάτω παύλα. Αυτό μπορεί να αναπαρασταθεί από την κανονική έκφραση [a-zA-Z_][a-zA-Z_0-9]* που σημαίνει «κάθε χαρακτήρας a-z, A-Z ή _, που ακολουθείται από 0 ή περισσότερα a-z, A-Z, _ ή 0-9».

Οι κανονικές εκφράσεις και οι μηχανές πεπερασμένων καταστάσεων που κατασκευάζουν δεν είναι αρκετά ισχυρές για να χειριστούν αναδρομικές δομές, όπως οι «n παρενθέσεις που ανοίγουν, που ακολουθούνται από μια εντολή, που ακολουθείται από n παρενθέσεις που κλείνουν». Σε αυτήν την περίπτωση, δε μπορούν να κρατήσουν κάπου τον αριθμό των παρενθέσεων που διαβάζονται, ώστε να βεβαιωθούν ότι το n είναι το ίδιο και στις δύο πλευρές — εκτός και αν το n μπορεί να παίρνει μόνο συγκεκριμένες τιμές. Γενικά χρειάζεται ένας πιο πολύπλοκος συντακτικός αναλυτής για να αναγνωρίσει τέτοιες δομές. Ένας συντακτικός αναλυτής μπορεί να βάζει τις παρενθέσεις σε μια στοίβα και στη συνέχεια να τις αφαιρεί, και στο τέλος να ελέγχει αν η στοίβα είναι άδεια (βλ. παράδειγμα).

Το εργαλείο Lex και ο μεταγλωττιστής του έχουν σχεδιαστεί ώστε να παράγουν κώδικα για γρήγορους λεκτικούς αναλυτές με βάση μια τυπική περιγραφή της λεκτικής σύνταξης. Γενικά δε θεωρείται αρκετά ισχυρό εργαλείο για εφαρμογές με πολύπλοκο σύνολο λεκτικών κανόνων και απαιτήσεις ταχύτητας. Για παράδειγμα, ο gcc χρησιμοποιεί λεκτικούς αναλυτές γραμμένους στο χέρι.

Παραπομπές

• Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X624
• Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
• Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6
• Sebesta, R. W. (2006). Concepts of programming languages (Seventh edition) pp. 177. Boston: Pearson/Addison-Wesley.

Δείτε επίσης

• Συντακτική ανάλυση

Εξωτερικοί σύνδεσμοι

• Λεκτική ανάλυση, Μεταγλωττιστές, ΘΠ06, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών.